package offer;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * @Author Elephas
 * @Date 2022/3/19
 **/
public interface TopKFrequent {
    int[] topKFrequent(int[] nums, int k);
}

class TopKFrequentTest{
    static final int[] TEST_01 = new int[]{1,2};

    public static void main(String[] args) {
        new TopKFrequentImpl1().topKFrequent(TEST_01, 2);
    }
}

class TopKFrequentImpl1 implements TopKFrequent{

    @Override
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        for(int num : nums){
            int freq = freqMap.getOrDefault(num, 0);
            freqMap.put(num, freq + 1);
        }
        int[][] elemMap = new int[freqMap.size()][];
        AtomicInteger i = new AtomicInteger(0);
        freqMap.forEach((key, value) -> elemMap[i.getAndIncrement()] = new int[]{value, key});
        Arrays.sort(elemMap, (o1, o2) -> o2[0] - o1[0]);

        List<Integer> ans = new ArrayList<>();
        ans.add(elemMap[0][1]);
        int rank = 1, count = 1;

        // 频率可能有并列第i个，需要处理并列情况
        for(int j = 1; j < elemMap.length; j++){
            if(elemMap[j][0] != elemMap[j - 1][0]){
                rank += count;
                count = 1;
            }else{
                count++;
            }
            if(rank <= k){
                ans.add(elemMap[j][1]);
            }else{
                break;
            }
        }
        return ans.stream().mapToInt(e -> e).toArray();
    }
}
